Methods

Author: Julien Dorier, Bioinformatics Competence Center, University of Lausanne, 1015 Lausanne, Switzerland

Cell tracking

Terminology:

Terminology is illustrated in Figure 1:

Terminology
Figure 1: Terminology.

Cell tracking graph: creation

The cell tracking graph is created by assigning one vertex to each labelled region (one vertex per time frame) and one edge between each overlapping pair of labelled region (considering only pairs of labelled region separated by not more than NtN_\text{t} time frames). The overlap area is stored as an edge attribute. An example of cell tracking graph obtained with Nt=2N_\text{t}=2 is shown in Figure 2.

Note: NtN_\text{t} is called "Max delta frame" in the GUI and max_delta_frame in the code.

Cell tracking graph creation
Figure 2: . Top: mask with labelled regions (color) overlaid on top of bright-field image. Bottom: cell tracking graph (obtained with Nt=2). Vertex color denotes the corresponding labelled region and edge thickness denotes the overlap area. Horizontal axis corresponds to time

Relabelling

As illustrated in Figure 2, labelled region are usually obtained independently for each frame and labels (colors) do not match across time frames. To obtain consistent labels across time, we use the following iterative relabelling approach (see Figure 3):

  1. Labelled regions (vertices) in the first time frame (t=0t=0) are arbitrarily relabelled using consecutive integer labels 11, 22, 33, \cdots (Figure 3A).

  2. We then iterate over the remaining time frames (Figure 3B-F).

The resulting relabelled cell tracking graph and mask are shown in Figure 4

Cell tracking graph relabelling
Figure 3: Iterative relabelling of the cell tracking graph. Panel A: first time frame (t=0) with corresponding vertices highlighted (white outline) and arbitrarily relabelled 1 (magenta) and 2 (green). Panels B-F: each panel corresponds to one time frame (t=1, ..., 5). Vertices corresponding to the current time frame are highlighted (white outline). Edge connecting vertices in the current time frame to vertices in previous time frames are shown in dark grey, together with the corresponding overlap area (black number). The confusion matrix is shown below the graph. Labels associated with each column/row are indicated (color). Matching between labels in the current time frame (rows) and labels in previous time frames (columns) by linear sum assignment is indicated using a bold font.
Relabelled cell tracking graph
Figure 4: Relabelled mask and cell tracking graph.

Cell tracking graph: cleaning

The final cell tracking graph is obtained by (see Figure 5):

The resulting final cell tracking graph is shown in Figure 7.

Note: The threshold ff used to filter out edges corresponding to low overlap is called "Min overlap fraction" in the GUI and min_overlap_fraction in the code.

Cell tracking graph cleaning
Figure 5: Cell tracking graph cleaning. Dashed grey lines denote edges corresponding to low overlap and solid light grey lines denotes redundant edges.
missing edges
Figure 6: Adding missing edges (blue). This made-up example is not related to Figure 5.
Final cell tracking graph
Figure 7: Final cell tracking graph.

Correction of segmentation errors

Mask interpolation

Cell segmentation tools (e.g. cellpose) may occasionally produce errors (e.g. time frames 3 and 4 in Figure 8A). When segmentation errors are punctual and surrounded (in time) by stable and error-free time frames, it is possible to correct the error using the information contained in neighboring time frames ("interpolating" neighboring time frames).

To "interpolate" a set of labelled regions (labels 1=green and 2=red in Figure 8) over a range of time frames (t=3 and t=4 in Figure 8) using the information contained in NiN_\text{i} neighbouring frames on each side (Ni=3N_\text{i}=3 by default), we start by evaluating the signed distance map for each labelled region and each time frame separately (Figure 8B and 8D). Each pixel in the distance map contain pixel the signed distance from this pixel to the boundary of the labelled region, with positive distance inside the labelled region and negative distances outside. For each selected labelled region and each selected time frame, we evaluate the median of all distance maps for the labelled region at time frames within ±Ni\pm N_\text{i} of the selected time frame (Figure 8C and 8E).

For each selected time frame, new labelled regions are obtained by assigning each pixel to the label with highest positive median distance map (Figure 8F). Pixels with negative median distance for all labelled regions are assigned to the background.

The final mask is obtained by erasing (i.e setting to background label) selected labelled regions in selected time frames (Figure 8G) and pasting non-background pixels from the new labelled regions (Figure 8F) onto the final mask (Figure 8H).

Note: NiN_\text{i} is called "Max delta frame (interpolation)" in the GUI and max_delta_frame_interpolation in the code.

Mask correction
Figure 8: Mask correction. A: mask (overlaid on top of bright-field image) and corresponding cell tracking graph with segmentation errors in time frames 3 and 4 (made-up example). B: distance maps for labelled region 1. All pixels of the distance map at time frame 3 (missing labelled region) are set to minus infinity. C: median distance maps for labelled region 1. D and E: same as B and C but for labelled region 2. F: updated labelled regions 1 and 2 obtained by combining median distance maps. G: original mask (A) after setting labelled regions 1 and 2 to background for selected time frames 3 and 4. H: Final mask (overlaid on top of bright-field image) and corresponding cell tracking graph after merging masks F and G.

Automatic correction of punctual defects

The previous "mask interpolation" method can be applied to any user selected set of labelled regions and time frames. However, it may not give reasonable results if the labelled regions are not stable enough within ±Ni\pm N_\text{i} time frames around the frames to be corrected.

Intuitively, this method should work best for punctual segmentation errors (i.e. spanning only few time frames), surrounded by enough stable and error-free time frames. To automatically find this type of segmentation defects, we use the information contained in the cell tracking graph:

Stable regions: Intuitively, a stable region of the cell tracking graph is a series of vertices in consecutive time frames (no missing time frame), all corresponding to the same mask label, each with a unique incoming and a unique outgoing edge (no branching).

More precisely, we start by flagging all edges of the cell tracking graph as stable or not stable. An edge is defined as stable if and only if it satisfies all the following criteria (Figure 9):

Examples of not stable edges are shown in Figure 9 (blue letters):

Mask correction
Figure 9: Examples of stable (dark grey) and not stable (light grey) edges. Vertex color denotes the corresponding label and edge thickness denotes the overlap area.

Stable regions are found as the connected components of the subgraph induced by all stable edges. The size of each stable region is measured as the number of vertices in connected component (Figure 10).

Mask correction
Figure 10: Size (red text) of stable regions (dark grey edges, colored vertices).

Punctual defects: Candidate defects are found as the connected components of the subgraph induced by all not stable edges (ignoring trivial components of size 1).

This initial list of candidate defects (connected components) is then filtered out to keep only punctual defects surrounded by stable regions, satisfying all the following criteria (see Figure 11):

Figure 11 and 12 show exemples of candidate defects. For Nd=2N_\text{d}=2 and Ns=3N_\text{s}=3, the following candidate defects would be filtered out:

Mask correction
Figure 11: Candidate defects (dark grey edges, colored vertices, identified with blue letters). Sizes of neighboring stable regions are indicated in red.
Mask correction
Figure 12: Labelled regions (made-up examples) corresponding to the candidate defects in Figure 11.

Finally, for each remaining defect in the list, the mask interpolation method described in the previous section is applied to the list of all labels appearing in the defect, for all time frames covered by the defect except first and last time frame (Figure 13).

Mask correction
Figure 13: Mask interpolation method applied to punctual defects (figure 11). The mask interpolation method is applied to all labels appearing in the defect and all highlighted time frames (light blue).

Notes:

Implementation

For the GUI: